//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
//
// 示例 1： 
//
// 输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
// 
//
// 示例 2： 
//
// 输入: "cbbd"
//输出: "bb"
// 
// Related Topics 字符串 动态规划

package com.yun.leetcode.editor.cn;

public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring().new Solution();
        System.out.println(solution.longestPalindrome("babad"));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String longestPalindrome(String s) {
            if (s.isEmpty()) {
                return "";
            }
            int length = s.length();
            if (length == 1) {
                return s;
            }
            int longest = 1;
            int start = 0;
            int[][] dp = new int[length][length];
            for (int i = 0; i < length; i++) {
                dp[i][i] = 1;
                if (i < length - 1) {
                    if (s.charAt(i) == s.charAt(i + 1)) {
                        dp[i][i + 1] = 1;
                        start = i;
                        longest = 2;
                    }
                }
            }
            for (int l = 3; l <= length; l++) {  //l表示检索的子串长度，等于3表示先检索长度为3的子串
                for (int i = 0; i + l - 1 < length; i++) {
                    int j = l + i - 1;  //终止字符位置
                    if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1] == 1) {  //状态转移
                        dp[i][j] = 1;  //是一，不是字母l
                        start = i;
                        longest = l;
                    }
                }

            }
            return s.substring(start, start + longest);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    // 思路：肯定暴力是可以解的，循环，从当前位置左右扩散，不断记录更新最长的字串。
    // 判断回文串还是得从两侧往中间判断，中间判断，第一步就有分支，最中间是重复还是不重复的问题，上面这个思路是n2复杂度，略优于最暴力解法

}